package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题


	   [
            [1],
    	   [1,1],
   		  [1,2,1],
  		 [1,3,3,1],
 		[1,4,6,4,1]
	   ]
	Given an index k, return the kth row of the Pascal's triangle.
	
	For example, given k = 3,
	Return [1,3,3,1].
	
	Note:
	Could you optimize your algorithm to use only O(k) extra space?
题目大意

	Pascal's_Triangle：就是杨辉三角
		给定行号,返回该行的元素
解题思路
	直接使用 @_118_Pascals_Triangle
	TODO：Could you optimize your algorithm to use only O(k) extra space?
 * @Date 2017-09-14 09：55
 */
public class _119_Pascal_s_Triangle_II {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	/**
	 * 得到行号
	 * 	My：
	 * @param rowIndex
	 * @return
	 */
    public List<Integer> getRow(int rowIndex) {
    	List<List<Integer>> tri = generate(rowIndex+1);
    	return tri.get(tri.size()-1);
    }
	
	
	/**
	 * 生成杨辉三角
	 * @param numRows
	 * @return
	 */
	public List<List<Integer>> generate(int numRows) {  
		List<List<Integer>> rs = new ArrayList<>();
		if (numRows == 0)	return rs;
		List<Integer> pre =  new ArrayList<>();		//前一行
		pre.add(1);											//第一行
		rs.add(pre);
		//从第二行开始遍历
		for (int i = 2; i <= numRows; i ++) {
			List<Integer> curRows =  new ArrayList<>();
			curRows.add(1);
			for (int j = 0; j < pre.size()-1; j ++) {
				curRows.add(pre.get(j)+pre.get(j+1));
			}
			curRows.add(1);	
			rs.add(curRows);
			pre = curRows;
		}
//		traverse(rs);
		return rs;
	}
	
	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	private TreeNode newTree1() {
		return new TreeNode(1, 
					null, null
				);
	}
	
	
	//中序遍历：看下结果
    public void traverse (ArrayList<ArrayList<Integer>> rs) {
    	for (ArrayList<Integer> row : rs) {
    		for (int i : row) {
    			LogUtils.print(i);
    		}
    		LogUtils.br();
    	}
    }
	
	
	public static void main(String[] args) {
		_119_Pascal_s_Triangle_II obj = new _119_Pascal_s_Triangle_II();
		LogUtils.println("结果", 
				obj.generate(
						5
				));
	}
}
